#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<set>

using namespace std;

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    vector<double> res;
    multiset<double> s(nums.begin(), nums.begin() + k);
    auto mid = next(s.begin(), k / 2);
    for (int i = k;; i++)
    {
        res.push_back((*mid + *next(mid, k % 2 - 1)) / 2);
        if (i == nums.size())    break;

        s.insert(nums[i]);
        if (nums[i] < *mid)  mid--;
        if (nums[i - k] <= *mid)   mid++;

        s.erase(s.find(nums[i - k]));
    }
    return res;
}

int main()
{
    vector<int> v = { 1,3,-1,-3,5,3,6,7 };
    auto res = medianSlidingWindow(v, 3);
    for (auto it : res)
        cout << it << endl;
    return 0;
}